package Sort.MergeSort;

/**
 * @program: jvm
 * @description
 * @author: tkk fendoukaoziji
 * @create: 2019-05-16 09:30
 **/
public class MergeSort {
    private long[] arr;
    private int elmeS;
    public MergeSort(int max){
        arr=new long[max];
        elmeS=0;
    }
    public void insert(long value){
        arr[elmeS]=value;
        elmeS++;
    }

    public void display(){
        for (int i = 0; i < elmeS; i++) {
            System.out.print(arr[i]+" ");
        }
        System.out.println("");
    }


    public void mergeSort(){
        long[] wordSpace = new long[elmeS];
        recMergeSort(wordSpace,0,elmeS-1);
    }

    private void recMergeSort(long[] wordSpace, int start, int end) {
        if(start==end){
            return;
        }else{
            int mid=(start+end)/2; //找到中点，划分子序列
            recMergeSort(wordSpace,start,mid);
            recMergeSort(wordSpace,mid+1,end);
            merge(wordSpace,start,mid+1,end);
        }
    }

    private void merge(long[] wordSpace, int startP, int hightP, int endP) {
        int j=0;
        int lowerBound=startP;
        int mid=hightP-1;
        int n=endP-startP+1; // 多少个元素个数
        while(startP<=mid&& hightP<=endP){
            if(arr[startP]<arr[hightP]){
                wordSpace[j++]=arr[startP++];
            }else{
                wordSpace[j++]=arr[hightP++];
            }
        }
        while (startP<=mid){
            wordSpace[j++]=arr[startP++];
        }
        while (hightP<=endP){
            wordSpace[j++]=arr[hightP++];
        }
        for ( j=0;j<n; j++) {
            arr[lowerBound+j]=wordSpace[j];
        }
    }

    public static void main(String[] args) {
        int maxSize=100;
        MergeSort arr;
        arr=new MergeSort(maxSize);
        arr.insert(64);
        arr.insert(21);
        arr.insert(33);
        arr.insert(70);
        arr.insert(12);
        arr.insert(85);
        arr.insert(44);
        arr.insert(3);
        arr.insert(99);
        arr.insert(0);
        arr.insert(108);
        arr.insert(36);

        arr.display();
        arr.mergeSort();
        arr.display();




    }


}

























